function twoSum(nums: number[], target: number): number[][] {
  let left = 0;
  let right = nums.length - 1;
  const result = [];
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      // 去重
      if (left > 0 && nums[left] === nums[left - 1]) {
        left++;
        right--;
        continue;
      }
      result.push([nums[left], nums[right]]);
      // 找到解 循环继续
      left++;
      right--;
    } else if (sum < target) {
      // 小了
      left++;
    } else {
      right--;
    }
  }
  return result;
}

function threeSum2(nums: number[], target: number): number[][] {
  // 排序前 数组未定义 或者 长度小于三 无解
  if (!nums || nums.length < 3) return [];
  nums.sort((a, b) => a - b);
  // 排序后 如果元素都
  // if (nums.every((n) => n > 0)) return []
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    // 前后相同 跳过 排除重复解
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // console.log(i)
    // 算出另外两数和
    const target2 = target - nums[i];
    // 分割数组
    const list = nums.slice(i + 1, nums.length);
    // 将问题划分为求两数解
    // const result = twoSum(list, target)
    // console.log(list, target, twoSum(list, target))
    twoSum(list, target2).forEach((item) => {
      result.push([nums[i], ...item]);
    });
    // result.push([nums[i], ...twoSum(list, target)]);
  }
  // console.log(result);
  return result;
}

function fourSum(nums: number[], target: number): number[][] {
  if (!nums || nums.length < 4) return [];
  nums.sort((a, b) => a - b);
  // console.log(nums);
  // if(nums.every((n) => n>0)) return []
  const result = [];

  for (let i = 0; i < nums.length - 3; i++) {
    // console.log(i>0 && nums[i] === nums[i - 1])
    // console.log(nums,i)
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // console.log('????')
    const target2 = target - nums[i];
    // console.log(target2)
    // const list = nums.splice(i+1,nums.length)
    //    const a =  nums.splice(i--,1);

    const list = nums.slice(i + 1, nums.length);
    threeSum2(list, target2).forEach((item) => {
      // console.log(item)
      result.push([nums[i], ...item]);
    });
    // i--;
  }
  // console.log(result)
  return result;
}

const nums13 = [-3, -2, -1, 0, 0, 1, 2, 3],
  target8 = 0;
fourSum(nums13, target8);
